//输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 
//
// 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 
//
// 
//
// 示例 1： 
//
// 输入：target = 9
//输出：[[2,3,4],[4,5]]
// 
//
// 示例 2： 
//
// 输入：target = 15
//输出：[[1,2,3,4,5],[4,5,6],[7,8]]
// 
//
// 
//
// 限制： 
//
// 
// 1 <= target <= 10^5 
// 
//
// 
// Related Topics 数学 双指针 枚举 👍 449 👎 0

package leetcode.editor.offer;

import java.util.ArrayList;
import java.util.List;

class HeWeiSdeLianXuZhengShuXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new HeWeiSdeLianXuZhengShuXuLieLcof().new Solution();
        solution.findContinuousSequence(9);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] findContinuousSequence(int target) {
            int left = 1, right = 1;
            List<int[]> res = new ArrayList<>();
            for (; left < target; left++) {
                int sum = left;
                for (right = left + 1; right < target; right++) {
                    sum += right;
                    if (sum < target) {
                        // for已经加了
                    } else if (sum == target) {
                        // 此时相加大于了target，保存连续序列
                        int count = 0;
                        int[] array = new int[right - left + 1];
                        for (int i = left; i <= right; i++, count++) {
                            array[count] = i;
                        }
                        res.add(array);
                    } else if (sum > target) {
                        break;
                    }
                }
            }

            return res.toArray(new int[0][]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}
